home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 285_01 / conflict.c < prev    next >
Text File  |  1990-07-08  |  17KB  |  751 lines
  1. /* Find and resolve or report look-ahead conflicts for bison,
  2.    Copyright (C) 1984 Bob Corbett and Free Software Foundation, Inc.
  3.  
  4. BISON is distributed in the hope that it will be useful, but WITHOUT ANY
  5. WARRANTY.  No author or distributor accepts responsibility to anyone
  6. for the consequences of using it or for whether it serves any
  7. particular purpose or works at all, unless he says so in writing.
  8. Refer to the BISON General Public License for full details.
  9.  
  10. Everyone is granted permission to copy, modify and redistribute BISON,
  11. but only under the conditions described in the BISON General Public
  12. License.  A copy of this license is supposed to have been given to you
  13. along with BISON so you can know your rights and responsibilities.  It
  14. should be in a file named COPYING.  Among other things, the copyright
  15. notice and this notice must be preserved on all copies.
  16.  
  17.  In other words, you are welcome to use, share and improve this program.
  18.  You are forbidden to forbid anyone else to use, share and improve
  19.  what you give them.   Help stamp out software-hoarding!  */
  20.  
  21. #include <stdio.h>
  22.  
  23. #include "bison.h"
  24. #include "machine.h"
  25. #include "new.h"
  26. #include "files.h"
  27. #include "gram.h"
  28. #include "state.h"
  29. #include "conflict.h"
  30.  
  31. #define USG
  32.  
  33. #ifdef USG                    /* or Microsoft C v5.1 */
  34.  
  35. #include <memory.h>
  36. #define bcopy(src, dst, num) memcpy((dst), (src), (num))
  37.  
  38. #elif TURBOC
  39.  
  40. #include <mem.h>
  41. #define bcopy(src, dst, num) memcpy((dst), (src), (num))
  42.  
  43. #endif
  44.  
  45. #ifdef sparc
  46. #include <alloca.h>
  47. #endif
  48.  
  49. extern char **tags;
  50. extern int tokensetsize;
  51. extern char *consistent;
  52. extern short *accessing_symbol;
  53. extern shifts **shift_table;
  54. extern unsigned *LA;
  55. extern short *LAruleno;
  56. extern short *lookaheads;
  57. extern int verboseflag;
  58. /*  
  59. extern char *alloca ();
  60.  
  61.     synonym for malloc()? Drh 12/30/88
  62.     NOTE: under MSC 5.1, alloca() allocates from STACK, not heap,
  63.           and objects thus obtained can NOT be free()'d.
  64. */
  65. char any_conflicts;
  66. char *conflicts;
  67. errs **err_table;
  68. int expected_conflicts;
  69.  
  70.  
  71. static unsigned *shiftset;
  72. static unsigned *lookaheadset;
  73. static int src_total;
  74. static int rrc_total;
  75. static int src_count;
  76. static int rrc_count;
  77.  
  78. static debugflag = 1 ;
  79.  
  80. void initialize_conflicts()
  81. {
  82.   register int i;
  83. /*  register errs *sp; JF unused */
  84.  
  85.   conflicts = NEW2(nstates, char);
  86.   shiftset = NEW2(tokensetsize, unsigned);
  87.   lookaheadset = NEW2(tokensetsize, unsigned);
  88.  
  89.   err_table = NEW2(nstates, errs *);
  90.  
  91.   any_conflicts = 0;
  92.  
  93.   for (i = 0; i < nstates; i++)
  94.     set_conflicts(i);
  95. }
  96.  
  97.  
  98. void set_conflicts(state)
  99. int state;
  100. {
  101.   register int i;
  102.   register int k;
  103.   register shifts *shiftp;
  104.   register unsigned *fp2;
  105.   register unsigned *fp3;
  106.   register unsigned *fp4;
  107.   register unsigned *fp1;
  108.   register int symbol;
  109.  
  110.   if (consistent[state]) return;
  111.  
  112.   for (i = 0; i < tokensetsize; i++)
  113.     lookaheadset[i] = 0;
  114.  
  115.   shiftp = shift_table[state];
  116.   if (shiftp)
  117.     {
  118.       k = shiftp->nshifts;
  119.       for (i = 0; i < k; i++)
  120.     {
  121.       symbol = accessing_symbol[shiftp->shifts[i]];
  122.       if (ISVAR(symbol)) break;
  123.       SETBIT(lookaheadset, symbol);
  124.     }
  125.     }
  126.  
  127.   k = lookaheads[state + 1];
  128.   fp4 = lookaheadset + tokensetsize;
  129.  
  130.   /* loop over all rules which require lookahead in this state */
  131.   /* first check for shift-reduce conflict, and try to resolve using precedence  */
  132.  
  133.   for (i = lookaheads[state]; i < k; i++)
  134.     if (rprec[LAruleno[i]])
  135.       {
  136.     fp1 = LA + i * tokensetsize;
  137.     fp2 = fp1;
  138.     fp3 = lookaheadset;
  139.   
  140.     while (fp3 < fp4)
  141.       {
  142.         if (*fp2++ & *fp3++)
  143.           {
  144.         resolve_sr_conflict(state, i);
  145.         break;
  146.           }
  147.       }
  148.       }
  149.  
  150.   /* loop over all rules which require lookahead in this state */
  151.   /* Check for conflicts not resolved above.  */
  152.  
  153.   for (i = lookaheads[state]; i < k; i++)
  154.     {
  155.       fp1 = LA + i * tokensetsize;
  156.       fp2 = fp1;
  157.       fp3 = lookaheadset;
  158.  
  159.       while (fp3 < fp4)
  160.     {
  161.       if (*fp2++ & *fp3++)
  162.         {
  163.           conflicts[state] = 1;
  164.           any_conflicts = 1;
  165.         }
  166.     }
  167.  
  168.       fp2 = fp1;
  169.       fp3 = lookaheadset;
  170.  
  171.       while (fp3 < fp4)
  172.     *fp3++ |= *fp2++;
  173.     }
  174. }
  175.  
  176.  
  177.  
  178. /* Attempt to resolve shift-reduce conflict for one rule
  179. by means of precedence declarations.
  180. It has already been checked that the rule has a precedence.
  181. A conflict is resolved by modifying the shift or reduce tables
  182. so that there is no longer a conflict.  */
  183.  
  184. void resolve_sr_conflict(state, lookaheadnum)
  185. int state;
  186. int lookaheadnum;
  187. {
  188.   register int i;
  189.   register int mask;
  190.   register unsigned *fp1;
  191.   register unsigned *fp2;
  192.   register int redprec;
  193.   errs *errp = (errs *) malloc (sizeof(errs) + ntokens * sizeof(short));
  194.   short *errtokens = errp->errs;
  195.  
  196.   /* find the rule to reduce by to get precedence of reduction  */
  197.   redprec = rprec[LAruleno[lookaheadnum]];
  198.  
  199.   mask = 1;
  200.   fp1 = LA + lookaheadnum * tokensetsize;
  201.   fp2 = lookaheadset;
  202.   for (i = 0; i < ntokens; i++)
  203.     {
  204.       if ((mask & *fp2 & *fp1) && sprec[i])
  205.     /* shift-reduce conflict occurs for token number i and it has a precision.
  206.        The precedence of shifting is that of token i.  */
  207.     {
  208.       if (sprec[i] < redprec)
  209.         {
  210.           if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  211.           *fp2 &= ~mask;  /* flush the shift for this token */
  212.           flush_shift(state, i);
  213.         }
  214.       else if (sprec[i] > redprec)
  215.         {
  216.           if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  217.           *fp1 &= ~mask;  /* flush the reduce for this token */
  218.         }
  219.       else
  220.         {
  221.           /* Matching precedence levels.
  222.          For left association, keep only the reduction.
  223.          For right association, keep only the shift.
  224.          For nonassociation, keep neither.  */
  225.  
  226.           switch (sassoc[i])
  227.         {
  228.  
  229.         case RIGHT_ASSOC:
  230.               if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  231.           break;
  232.  
  233.         case LEFT_ASSOC:
  234.               if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  235.           break;
  236.  
  237.         case NON_ASSOC:
  238.               if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
  239.           break;
  240.         }
  241.  
  242.           if (sassoc[i] != RIGHT_ASSOC)
  243.         {
  244.           *fp2 &= ~mask;  /* flush the shift for this token */
  245.           flush_shift(state, i);
  246.         }
  247.           if (sassoc[i] != LEFT_ASSOC)
  248.             {
  249.           *fp1 &= ~mask;  /* flush the reduce for this token */
  250.         }
  251.           if (sassoc[i] == NON_ASSOC)
  252.         {
  253.           /* Record an explicit error for this token.  */
  254.           *errtokens++ = i;
  255.         }
  256.         }
  257.     }
  258.  
  259.       mask <<= 1;
  260.       if (mask == 0)
  261.     {
  262.       mask = 1;
  263.       fp2++;  fp1++;
  264.     }
  265.     }
  266.   errp->nerrs = errtokens - errp->errs;
  267.   if (errp->nerrs)
  268.     {
  269.       /* Some tokens have been explicitly made errors.  Allocate
  270.      a permanent errs structure for this state, to record them.  */
  271.       i = (char *) errtokens - (char *) errp;
  272.  
  273.       if (debugflag)
  274.         printf("CONFLICT.C:resolve_sr_conflict request %u bytes\n", i) ;
  275.  
  276.       err_table[state] = (errs *) mallocate ((unsigned int)i);
  277.       bcopy (errp, err_table[state], i);
  278.     }
  279.   else
  280.     err_table[state] = 0;
  281. }
  282.  
  283.  
  284.  
  285. /* turn off the shift recorded for the specified token in the specified state.
  286. Used when we resolve a shift-reduce conflict in favor of the reduction.  */
  287.  
  288. void flush_shift(state, token)
  289. int state;
  290. int token;
  291. {
  292.   register shifts *shiftp;
  293.   register int k, i;
  294. /*  register unsigned symbol; JF unused */
  295.  
  296.   shiftp = shift_table[state];
  297.  
  298.   if (shiftp)
  299.     {
  300.       k = shiftp->nshifts;
  301.       for (i = 0; i < k; i++)
  302.     {
  303.       if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
  304.         (shiftp->shifts[i]) = 0;
  305.     }
  306.     }
  307. }
  308.  
  309.  
  310.  
  311. void log_resolution(state, LAno, token, resolution)
  312. int state, LAno, token;
  313. char *resolution;
  314. {
  315.   fprintf(foutput,
  316.       "Conflict in state %d between rule %d and token